#pragma once

#include <iostream>
#include <vector>

namespace jianzhi_053
{

class Solution {
public:
    int search(const std::vector<int>& nums, int target)
    {
        int lower = -1;
        for (int left = 0, right = nums.size() - 1; left <= right; ) {
            int mid = (left + right) / 2;
            if (nums.at(mid) == target && (mid == 0 || nums.at(mid - 1) < target)) {
                lower = mid;
                break;
            } else if (nums.at(mid) < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if (lower < 0)
            return 0;

        int upper = -1;
        for (int left = 0, right = nums.size() - 1; left <= right; ) {
            int mid = (left + right) / 2;
            if (nums.at(mid) == target && (mid == (int)nums.size() - 1 || nums.at(mid + 1) > target)) {
                upper = mid;
                break;
            } else if (nums.at(mid) > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return upper - lower + 1;
    }

    int missingNumber(const std::vector<int>& nums)
    {
        for (int left = 0, right = nums.size() - 1; left <= right; ) {
            int mid = (left + right) / 2;
            if (mid < nums.at(mid) && (mid == 0 || mid - 1 == nums.at(mid - 1)))
                return mid;
            if (mid == nums.at(mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums.size();
    }
};

}  /* namespace jianzhi_053 */
